Discrete Mathematics
Q51.
Consider a simple undirected unweighted graph with at least three vertices. If A is the adjacency matrix of the graph, then the number of 3-cycles in the graph is given by the trace ofQ53.
The following simple undirected graph is referred to as the Peterson graph.Which of the following statements is/are TRUE?MSQQ54.
Let G be a simple undirected graph. Let TD be a depth first search tree of G. Let TB be a breadth first search tree of G. Consider the following statements. (I) No edge of G is a cross edge with respect to TD. (A cross edge in G is between two nodes neither of which is an ancestor of the other in TD.) (II) For every edge (u,v) of G, if u is at depth i and v is at depth j in TB, then |i-j|=1. Which of the statements above must necessarily be true?Q56.
Let f be a function from a set A to a set B, g a function from B to C, and h a function from A to C, such that h(a) = g(f(a)) for all a \in A. Which of the following statements is always true for all such functions f and g?Q57.
Let S denote the set of all functions f:{\{0,1\}}^{4} \rightarrow \{0,1\}. Denote by N the number of functions from S to the set {0,1}. The value of log_{2} log_{2}N is______.Q58.
Let R denote the set of real numbers. Let f:R\times R \rightarrow R \times R be a bijective function defined by f(x,y) = (x+y, x-y). The inverse function of f is given byQ59.
G is an undirected graph with vertex set {v1, v2, v3, v4, v5, v6, v7} and edge set {v1v2, v1v3, v1v4 ,v2v4, v2v5, v3v4, v4v5, v4v6, v5v6, v6v7 }. A breadth first search of the graph is performed with v1 as the root node. Which of the following is a tree edge?Q60.
Which of the properties hold for the adjacency matrix A of a simple undirected unweighted graph having n vertices?MSQ